class Solution {

    public static void main(String[] args) {
        ListNode n2 = new ListNode(2);
        ListNode n1 = new ListNode(1,n2);
        reorderList(n1);
    }

    public static void reorderList(ListNode head) {
        if (head.next == null) {
            return;
        }
        // 1、找到中间结点：快慢双指针
        ListNode slow = head, fast = head, tail = null; // tail记录第一个链表的尾
        while (fast != null && fast.next != null) {
            tail = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2、将后半部分链表逆序：三指针法
        ListNode prev = null, Next = slow.next;
        while (slow != null) {
            // 修改指针指向
            slow.next = prev;
            // 更新指针
            prev = slow;
            slow = Next;
            Next = Next == null ? null : Next.next;
        }
        // 3、合并两个链表
        // 得先将链表给分隔开来
        tail.next = null; // 将第一个链表与第二个链表断开
        ListNode cur = head, curNext = cur.next;
        slow = prev; // slow已经为null了，得更新为前一个
        ListNode slowNext = slow.next;
        int count = 0;
        while (cur != null && slow != null) { // cur链表的最后一个结点指针不是指向null
            if (count % 2 == 0) { // 第一个链表作为头
                cur.next = slow;
                cur = curNext;
                curNext = curNext == null ? null : curNext.next;
            } else { // 第二个链表作为头
                slow.next = cur;
                slow = slowNext;
                slowNext = slowNext == null ? null : slowNext.next;
            }
            count++;
        }
    }
}


class ListNode {
    int val;
    ListNode next;

    public ListNode() {

    }

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
